package org.dna.opdracht2;

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.util.Random;

public class RSHeap {
	private int heapsize;
	private int deadspace;
	private int currentsize;
	private int[] elements;
	
	private int totalruns;
	private int totalnumbers;
	
	private String inputFile;
	private String outputFile;
	
	private BufferedReader inputFileReader;
	
	public RSHeap(int heapsize) {
		this.heapsize = heapsize;
		deadspace = 0;
		currentsize = 0;
		elements = new int[heapsize];
		
		inputFile = "input.txt";
		outputFile = "output.txt";
		
		totalruns = 1;
		totalnumbers = 10;
		
		try {
			inputFileReader = new BufferedReader(new FileReader(inputFile));
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		}
	}
	
	public void insert(int value) {
		if(currentsize == heapsize) {
			throw new RuntimeException("Heap is full");
		}
		
		int index = currentsize;
		currentsize++;
		
		while(index > 0 && elements[(index - 1) / 2] > value) {
			elements[index] = elements[(index - 1) / 2];
			index = (index - 1) / 2;
		}
		
		elements[index] = value;
	}
	
	public boolean isEmpty() {
		return currentsize == 0;
	}
	
	public int deleteMin() {
		int first = elements[0];
		elements[0] = elements[--currentsize];
		percolateDown(0);
		
		return first;
	}
	
	private void percolateDown(final int index) {
		final int left = index * 2 + 1;
		final int right = index * 2 + 2;
		int smallest;
		
		if(left < currentsize) {
			smallest = left;
			if(right < currentsize){
				smallest = elements[right] > elements[left] ? left : right;
			}
		
			if(elements[index] > elements[smallest]) {
				int tmpValue = elements[smallest];
				elements[smallest] = elements[index];
				elements[index] = tmpValue;
				
				percolateDown(smallest);
			}
		}
	}
	
	public void buildheap() {
		buildheap(currentsize);
	}
	
	public void buildheap(int index) {
		for (int i = index / 2 - 1; i >= 0; i--) {
			percolateDown(i);
		}
	}
	
	public void printElements() {
		for(int i = 0; i < currentsize; i++) {
			System.out.println("elements["+ i +"]: "+ elements[i]);
		}
	}
	
	private void fillHeap() {
		try {
			String line = null;
			for(int i = 0; i < heapsize; i++) {
				if((line = inputFileReader.readLine()) != null) {
					insert(Integer.parseInt(line));
				}
			}
		} catch (NumberFormatException | IOException e) {
			e.printStackTrace();
		}
	}
	
	
	public void readFile() {
		fillHeap();
		
		int smallest = -1;
		String line = null;
		FileWriter writer = null;
		
		try {
			writer = new FileWriter(outputFile);
			while((line = inputFileReader.readLine()) != null) {
				smallest = deleteMin();
				writer.write(smallest +"\r\n");
				
				int next = Integer.parseInt(line);
				if(next >= smallest) {
					insert(next);
				} else {
					deadspace++;
					elements[currentsize] = next;
				}
				
				if(isEmpty()) {
					writer.write("#############################\r\n");
					currentsize = deadspace;
					buildheap(deadspace); // Deadspace elementen staan nu weer in de "gewone" heap
					deadspace = 0;
					totalruns++;
				}
			}
			
			while(!isEmpty()) {
				writer.write(deleteMin() +"\r\n");
			}
			
			if(deadspace > 0) {
				if(deadspace == heapsize) {// Als de heap helemaal volstaat met deadspace elementen hoeven
					// we alleen nog maar te rebuilden.
					buildheap(heapsize);
				} else {
					// Als de heap niet compleet volstaat met deadspace elementen
					// voeg dan de elementen vanaf het eerste deadspace element weer
					// vooraan in de array.
					for(int i = (heapsize - deadspace); i < heapsize; i++) {
						insert(elements[i]);
					}
				}
				
				writer.write("#############################\r\n");
				
				while(!isEmpty()) {
					writer.write(deleteMin() +"\r\n");
				}
				
				totalruns++;
			}
			
		} catch(IOException e) {
			e.printStackTrace();
		} finally {
			if(writer != null) {
				try {
					writer.flush();
					writer.close();
				} catch(IOException e) {
					e.printStackTrace();
				}
			}
		}
	}
	
	public void generateRandomNumbers(int total, int maxValue) {
		FileWriter writer = null;
		
		try {
			writer = new FileWriter(inputFile);
			Random random = new Random();
			
			for(int i = total; i > 0; i--) {
				writer.append((int)random.nextInt(maxValue) + 1 +"\r\n");
			}
		} catch(IOException e) {
			e.printStackTrace();
		} finally {
			if(writer != null) {
				try {
					writer.close();
				} catch(IOException e) {
					e.printStackTrace();
				}
			}
		}
	}
	
	public int getTotalRuns() {
		return totalruns;
	}
	
	public void setTotalNumbers(int totalnumbers) {
		this.totalnumbers = totalnumbers;
	}

	// Controleer of de nummers in output.txt wel goed gesorteerd zijn. Elke run
	// word apart gecontroleerd, runs zijn gescheiden door '#############################'.
	// Daarna word gekeken of het aantal nummers (zonder scheidingsteken) gelijk is aan
	// de parameter totalnumbers.
	public boolean isSorted() {
		String line = null;
		try {
			inputFileReader = new BufferedReader(new FileReader(outputFile));
		} catch (FileNotFoundException e1) {
			e1.printStackTrace();
		}
		
		int previous = -1;
		int totalnumbers = 0;
		try {
			while((line = inputFileReader.readLine()) != null) {
				if(line.equals("#############################")) {
					previous = -1;
					continue;
				}
				
				int number = Integer.parseInt(line);
				if(number >= previous) {
					previous = number;
					
					totalnumbers++;
					continue;
				}
				
				return false;
			}
		} catch(IOException e) {
			e.printStackTrace();
		}

		return totalnumbers == this.totalnumbers;
	}
}
